#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "uthash.h"

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
};
typedef struct TreeNode treeNode, *treenode;

typedef struct my_hash {
	int id_val; // key
	int idx;
	UT_hash_handle hh;
} HashMap, *hashMap;

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize);
treenode buildTreeAux(int* preorder, int sIdxP, int eIdxP, int* inorder, int sIdxI, int eIdxI);

hashMap map;
int main()
{
	return 0;
}

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize)
{
	map = NULL;
	for (int i = 0; i < inorderSize; i++) {
		hashMap s = (hashMap)malloc(sizeof(HashMap));
		HashMap t = { inorder[i], i, NULL };
		*s = t;
		HASH_ADD_INT(map, id_val, s);
	}
	return buildTreeAux(preorder, 0, preorderSize, inorder, 0, inorderSize);
}

treenode buildTreeAux(int* preorder, int sIdxP, int eIdxP, int* inorder, int sIdxI, int eIdxI)
{
	if (sIdxP >= eIdxP) return NULL;

	int rootPre = sIdxP;
	hashMap s; HASH_FIND_INT(map, preorder + rootPre, s);
	int rootIn = s->idx;

	treenode root = (treenode)malloc(sizeof(treeNode));
	root->val = preorder[rootPre];

	int leftLen = rootIn - sIdxI;
	root->left = buildTreeAux(preorder, sIdxP + 1, sIdxP + leftLen + 1,
			inorder, sIdxI, rootIn);
	root->right = buildTreeAux(preorder, sIdxP + leftLen + 1, eIdxP,
			inorder, rootIn + 1, eIdxI);

	return root;
}
